package com.hsp.struct.queue;

import java.util.Scanner;

/**
 * @version 1.0
 * @Author: xxl　
 * @Date: 2021/9/27 14:07
 * 使用数组模拟环形队列  front 队列头  rear 队列尾部  %取余运算
*  当队列满时,入队列执行是否为满的条件判断 此时有 rear = front 有(arr[rear + 1]  = arr[0]),
 *  此时与队列为空判断 rear = front 条件一致,无法判断队列是空还是满, 所以需要一个数组空间作为标识
 * 当 (rear + 1) % maxSize = front 队列容量满
 * 当 rear = fornt 队列空
 *  参考
 *  Java -韩顺平 图解Java 数据结构 和 算法-尚硅谷_哔哩哔哩_bilibili https://www.bilibili.com/video/BV1B4411H76f?p=15
 * 数组实现环形队列Java - SegmentFault 思否 https://segmentfault.com/a/1190000022804140
 */
public class CircleArrayQueue {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入数组长度长度,(队列实际长度为数组长度-1)");
        int maxSize = scanner.nextInt();
        CircleArrayQueue circleQueue = new CircleArrayQueue(maxSize);
        boolean loop = true;
        while (loop) {
            System.out.println("s(show) 显示队列");
            System.out.println("a(add)  加入队列");
            System.out.println("g(get)  取出队列");
            System.out.println("h(head) 查看队列头");
            System.out.println("e(head) 退出队列");
            char c = scanner.next().charAt(0);
            switch (c) {
                case 's':
                    circleQueue.show();
                    break;
                case 'a':
                    System.out.println("请输入一个数");
                    int i = scanner.nextInt();
                    circleQueue.add(i);
                    break;
                case 'g':
                    try {
                        int queueNum = circleQueue.get();
                        System.out.println("取出队列值:" + queueNum);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int headNum = circleQueue.head();
                        System.out.println(headNum);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    System.out.println("退出");
                    loop = false;
                    break;
                default:
                    break;
            }
        }

    }
    
    /**
     * 队列头 初始值为0,起始位置为数组的第一个元素
     */
    private int front;
    /**
     * 队列尾 初始值为0, 步长为n+1
     */
    private int rear;
    /**
     * 队列容量
     */
    private int maxSize;
    /**
     * 队列存储数组, 长度 = maxSize + 1
     */
    private int[] arr;

    /**
     * 初始化队列
     * @param maxSize
     */
    public CircleArrayQueue(int maxSize){
        this.front = 0;
        this.rear = 0;
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
    }

    /**
     * 判断队列是否满
     * @return
     */
    public boolean isFull() {
        return (this.rear + 1) % maxSize == front;
    }

    /**
     * 判断队列是否空
     * @return
     */
    public boolean isEmpty() {
        return  this.rear == this.front;
    }

    /**
     * 入队列
     * @param num
     */
    public void add(int num) {
        if(isFull()){
            System.out.println("队列已满");
            return;
        }
        this.arr[this.rear] = num;
        // rear 后移动需要考虑取模, 当队列首次存满并取出后,当再次存入时 rear = maxSize +1
        this.rear = (this.rear + 1) % maxSize;
        System.out.println("rear :" + this.rear);
    }

    /**
     * 出队列
     * @return
     */
    public int get() {
        if(isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        int num = this.arr[front];
        // front 后移与rear同理
        this.front = (this.front + 1) % maxSize;
        return num;
    }

    /**
     * 当前队列有效数据个数
     * @return
     */
    public int size() {
        return  (this.rear + this.maxSize - this.front) % this.maxSize;
    }

    /**
     * 输出队列有效数据
     */
    public void show() {
        if(isEmpty()) {
            System.out.println("队列为空");
        }

        for( int iterator = this.front  ; iterator < front + this.size() ; iterator++) {
            int index = iterator % maxSize;
            System.out.printf("arr[%d] = %d\n", index, this.arr[index]);
        }
    }

    /**
     * 取队列头
     */
    public int head() {
        if(isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return  this.arr[this.front % maxSize];
    }
}
